# -*- coding:utf-8 -*-
'''
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
平衡二搜索树 就是左大于中大于右 然后左右深度之差不可以超过1

解题思路 ： 利用递归max（left，right）+1 求最大深度然后递归判断左右深度差
'''
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
     def IsBalanced_Solution(self, root):
        if not root: return True
        if abs(self.maxDepth(root.left) - self.maxDepth(root.right)) > 1:
            return False
        return self.IsBalanced_Solution(root.left) and self.IsBalanced_Solution(root.right)
     def maxDepth(self,root):
        if not root: return 0
        return max(self.maxDepth(root.left),self.maxDepth(root.right))+1

     def midOrder(self, root):
        if not root: return True
        self.midOrder(root.left)
        self.stack.append(root.val)
        self.midOrder(root.right)
     def isBST(self,root):
        self.stack = []
        self.midOrder(root)
        for i in range(1, len(self.stack)):
            if self.stack[i-1] > self.stack[i]:
                return False
        return True